Tags: loop invariants, binary search
Consider iterative_binary_search below and note the print statement in the while-loop:
import math
def iterative_binary_search(arr, target):
start = 0
stop = len(arr)
while (stop - start) > 0:
print(arr[start])
middle = math.floor((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] > target:
stop = middle
else:
start = middle + 1
return None
Suppose iterative_binary_search is run on the array:
[-202, -201, -200, -50, -20, -10, -4, -3, 0, 1, 3, 5, 6, 7, 9, 10, 12, 15, 22]
with target 11.
What will be the last value of arr[start] printed?
10
Tags: loop invariants, binary search
Consider the iterative implementation of binary search shown below:
import math
def iterative_binary_search(arr, target):
start = 0
stop = len(arr)
while (stop - start) > 0:
print(arr[start])
middle = math.floor((start + stop) / 2)
if arr[middle] == target:
return middle
elif arr[middle] > target:
stop = middle
else:
start = middle + 1
return None
Which of the following loop invariants is true, assuming that arr is sorted and non-empty, and target is not in the array? Select all that apply.
The first option is correct.
Tags: loop invariants, selection sort
Suppose you are sorting an array using selection sort. At the current iteration of selection sort, the array being sorted looks like this:
[0, 1, 2, 2, 3, 4, 2, 10, 13, 4]
Which of the following are possible options for how many times the outer for loop has run? Select all that apply.
1, 2, 3, and 4. Remember the selection sort loop invariants: after the \(\alpha\)th iteration, the first \(\alpha\) numbers are \(\leq\) the remaining numbers, and the first \(\alpha\) numbers are in sorted order.
To answer this question, we can ask, for each \(\alpha\), are the loop invariants true? If yes, then it is possible that \(\alpha\) iterations have been made; if not, then it is not possible.
It is true for \(\alpha=1\), since the first number is \(\leq\) the remaining numbers, and the first 1 numbers are in sorted order. Same for \(\alpha = 2, 3, \) and \(4\). However, it is not true at \(\alpha = 5\). One of the loop invariants is true (the first five numbers are in sorted order), but the other is not: the first 5 numbers are not all \(\leq\) the remaining numbers. In particular, the fifth number (3) is not \(\leq\) the 7th number (2). Therefore, this could not possibly be the result after 5 iterations.
Tags: loop invariants
Consider this code which partitions a list in a special way:
def is_even(i):
"""Returns True if i is even, False otherwise."""
return i % 2 == 0
def mystery_partition(numbers):
def swap(i, j):
numbers[i], numbers[j] = numbers[j], numbers[i]
barrier_ix = 0
for i in range(len(numbers)):
if is_even(numbers[i]):
swap(i, barrier_ix)
if numbers[barrier_ix] > numbers[0]:
swap(0, barrier_ix)
barrier_ix += 1
Which of the following loop invariants are true for this code? Select all that apply.
Note: any statement about an empty set or list is considered to be automatically true.
1st option: After each iteration of the for loop, all numbers in numbers[:barrier_ix] are even.
3rd option: After each iteration of the for loop, numbers[0] is greater than or equal to all numbers in numbers[:barrier_ix].
Tags: loop invariants, quickselect
Recall the partition operation from quickselect. Which of the following arrays could have been partitioned at least once? Select all that apply.
The second, third, and last all should be selected.